#include <bits/stdc++.h>

using namespace std;

typedef class Node {
public:
    int content;
    Node *next;
    Node(int content = 0) {
        this->content = content;
        next = nullptr;
    }
}*Pnode;


class SinglyList {
public:
    SinglyList() {
        head = new Node(); // 此处使用一个头节点
        size = 0;
    }
    ~SinglyList() {
        for (Pnode p = head; p != nullptr; p = head) {
            head = p->next;
            delete p;
        }
    }

    // 删除pre_node的下一个节点  返回被删去的节点地址
    Pnode moveNode(Pnode pre_node) {
        Pnode to_delete = pre_node->next;
        pre_node->next = to_delete->next;
        size--;
        return to_delete;
    }

    // 头部添加节点 O(1)
    void addToHead(Pnode pnode) {
        pnode->next = head->next;
        head->next = pnode;
        size++;
    }

    // 尾部添加节点 O(n)
    void addToTail(Pnode pnode) {
        Pnode *p = &head;
        for (; *(p); p = &((*p)->next));
        *(p) = pnode;
        // Pnode p = head;
        // for (; p->next != nullptr; p = p->next);
        // p->next = pnode;
        size++;
    }

    // 翻转链表 O(n)
    // head -> 0 -> 1 -> 2
    // head -> 2 -> 1 -> 0
    void reverse_list() {
        if (size == 0) return;
        Pnode bottom = head->next;
        while (bottom->next != nullptr) {
            addToHead(moveNode(bottom));
        }
    }

    void print() {
        for (Pnode p = head->next; p != nullptr; p = p->next) {
            cout << p->content << " ";
        }
        cout << endl;
    }
private:
    Pnode head;
    int size;
};

int main() {
    SinglyList *l = new SinglyList();
    for (int i = 0; i < 10; i++) {
        l->addToTail(new Node(i));
    }
    l->print();
    l->reverse_list();
    l->print();
    l->reverse_list();
    l->print();
    //system("pause");
    return 0;
}
